package com.hardy.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * 
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given[100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is[1, 2, 3, 4]. Return its length:4.
Your algorithm should run in O(n) complexity.
 * @author Administrator 2016��9��4�� ����9:31:07
 * @param
 * @return
 */
public class LongestConsecutiveSequence {

	public LongestConsecutiveSequence() {
		// TODO Auto-generated constructor stub
	}

	public static int longestConsecutive(int[] num) {
		Set<Integer> set=new HashSet<Integer>();
		for(int n:num){
			set.add(n);
		}
		
		int count=0;
		for(int i:num){
			if(set.remove(i)){
				int sum=1;
				int val=i;
				int maxVal=val+1;
				int minVal=val-1;
				while(set.remove(maxVal)){
					sum++;
					maxVal++;
				}
				while(set.remove(minVal)){
					sum++;
					minVal--;
				}
				count=Math.max(count, sum);
			}
		}
		return count;
	}
	
	public static void main(String[] args) {
		int[] num={100, 4, 200, 1, 3, 2};
		System.out.println(longestConsecutive(num));
	}
}
